#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run30.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/8 0008 14:42
"""
"""
把只包含因子2、3和5的数称作丑数（Ugly Number）。例
如6、8都是丑数，但14不是，因为它包含因子7。 
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

"""


class Solution:
    def GetUglyNumber_Solution(self, index):
        if index < 7: return index
        res = [1, ]
        t2 = 0
        t3 = 0
        t5 = 0
        for i in range(1, index):
            res[i] = min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5))
            if (res[i] == res[t2] * 2): t2 += 1
            if (res[i] == res[t3] * 3): t3 += 1
            if (res[i] == res[t5] * 5): t5 += 1
        return res[index - 1]
